package leetcode.erfen;

/**
 *## 540
 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

 请你找出并返回只出现一次的那个数。

 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

 示例 1:

 输入: nums = [1,1,2,3,3,4,4,8,8]
 输出: 2
 示例 2:

 输入: nums =  [3,3,7,7,10,11,11]
 输出: 10

 */
public class SingleNonDuplicate {
    public int singleNonDuplicate2(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
                res = res^nums[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int [] arr = new int[]{3,3,2};
        System.out.println(new SingleNonDuplicate().singleNonDuplicate(arr));
    }
    public int singleNonDuplicate(int[] nums) {
        return find(nums,0,nums.length-1);
    }

    private int find(int[] nums,int i,int j){
        if(nums.length==1)
            return nums[0];
        int mid = i+(j-i)/2;
        if( (mid==0 && nums[mid]!=nums[mid+1]) || (mid== nums.length-1 && nums[mid]!=nums[mid-1])//边上位置
             || (nums[mid]!=nums[mid-1] &&  nums[mid]!=nums[mid+1]) )//中间位置
                return nums[mid];

        if(mid%2==0){//当前位置在偶数为
            if( (mid+1< nums.length && nums[mid]!=nums[mid+1]) ){//偶数位的时候，如果改变过了，后一个数和当前位置的数不相等
                return  find(nums,i, mid-1);//在后面
            }else
                return  find(nums,mid+1,j);
        }else {//当前位置在奇数为
            if( (mid+1< nums.length && nums[mid]==nums[mid+1]) ){//奇数位的时候，如果改变过了，后一个数和当前位置的数相等
                return  find(nums,i, mid-1);//在前面找
            }else
                return  find(nums,mid+1,j);
        }
    }
}